package first.codeTop.meituan;

/**
 * @ClassName Leetcode142
 * @description:
 * @author: 荣燊
 * @create: 2021-08-02 21:49
 **/
public class Leetcode142 {
    // 环形链表II
    public static void main(String[] args) {

    }

    /**
     * 分两个步骤，首先通过快慢指针的方法判断链表是否有环；接下来如果有环，则寻找入环的第一个节点。
     * 具体的方法为，首先假定链表起点到入环的第一个节点A的长度为a【未知】，
     * 到快慢指针相遇的节点B的长度为（a + b）【这个长度是已知的】。现在我们想知道a的值，
     * 注意到快指针p2始终是慢指针p走过长度的2倍，所以慢指针p从B继续走（a + b）又能回到B点，
     * 如果只走a个长度就能回到节点A。但是a的值是不知道的，解决思路是曲线救国，注意到起点到A的长度是a，
     * 那么可以用一个从起点开始的新指针q和从节点B开始的慢指针p同步走，
     * 相遇的地方必然是入环的第一个节点A。
     *
     * 画个图，就解决了
     */
    public static ListNode detectCycle(ListNode head) {
        // 先判断有没有环
        boolean flag = false;
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                flag = true;
                break;
            }
        }

        // 注意此时慢节点停留的位置，不一定是入环点
        if (flag) {
            ListNode p = head;
            while (p != slow) {
                p = p.next;
                slow = slow.next;
            }
            return p;
        }
        return null;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
